package com.sicheng.algorithm.string;

import java.util.HashMap;

public class 最小唯一子串 {
    /*
        76. 最小覆盖子串
        给你一个字符串 s 、一个字符串 t 。
        返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
    */
    public static void main(String[] args) {

//        System.out.println(minWindow("ADOBECODEBANC", "ABC"));
        System.out.println(minWindow("A", "A"));
    }

    public static String minWindow(String s, String t) {
        HashMap<Character, Integer> map = new HashMap<>();
        for (char ch : t.toCharArray()) {
            map.put(ch, map.getOrDefault(ch, 0) + 1);
        }
        int right = 0, left = 0;
        char charAtRight;
        int windowStart = 0;
        int windowLen = Integer.MAX_VALUE;
        while (right < s.length()) {
            charAtRight = s.charAt(right);
            if (map.containsKey(charAtRight))
                map.put(charAtRight, map.get(charAtRight) - 1);
            right++;
            while (check(map)) {
                if (right - left < windowLen) {
                    windowLen = right - left;
                    windowStart = left;
                }
                if (map.containsKey(s.charAt(left)))
                    map.put(s.charAt(left), map.get(s.charAt(left)) + 1);
                left++;
            }
        }
        if (windowLen != Integer.MAX_VALUE)
            return s.substring(windowStart, windowLen + windowStart);
        return "";
    }

    private static boolean check(HashMap<Character, Integer> map) {
        for (Integer value : map.values()) {
            if (value > 0)
                return false;
        }
        return true;
    }
}
